package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangjy
 * @description 验证二叉搜索树
 * <p>
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 * <p>
 * 有效 二叉搜索树定义如下：
 * <p>
 * 节点的左子树只包含 小于 当前节点的数。
 * 节点的右子树只包含 大于 当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 * <p>
 * 提示：
 * <p>
 * 树中节点数目范围在[1, 104] 内
 * -231 <= Node.val <= 231 - 1
 * @date 2025/3/5 19:30
 */
public class IsValidBST_98 {

    public static void main(String[] args) {

    }

    /**
     * dmsxl：递归-中序-双指针
     */
    TreeNode pre7 = null;

    public boolean isValidBST7(TreeNode root) {
        return dfs7(root);
    }

    public boolean dfs7(TreeNode node) {
        if (node == null) return true;

        // 左
        boolean left = dfs7(node.left);

        // 中
        // pre非空，且大于当前节点，表明不满足BST，直接返回
        if (pre7 != null && pre7.val > node.val) return false;
        // 其它情况，pre记录当前node的前一个节点
        pre7 = node;

        //右
        boolean right = dfs7(node.right);

        return left && right;
    }

    /**
     * 个人：参考dmsxl双指针
     * <p>
     * 思路：
     * 双指针，优化dmsxl，递归不能解决节点值有Long.MIN_VALUE的问题。
     * pre记录的是，在中序遍历结果中，当前节点node的前一个节点（并不一定是当前node的父节点）。
     */
    TreeNode pre6 = null;

    public boolean isValidBST6(TreeNode root) {
        return dfs6(root);
    }

    public boolean dfs6(TreeNode node) {
        if (node == null) return true;

        // 左
        boolean left = dfs6(node.left);

        // 中
        // 访问整个中序遍历第一个节点时（全局首个访问节点），它的pre是null，访问后，将pre更新成全局首个访问节点
        if (pre6 == null) {
            pre6 = node;
        } else {
            // 不是全局首个访问节点，则判断当前node节点值和pre（pre是当前node在中序遍历结果中的前一个节点，并不一定是当前node的父节点）
            // 若当前node > pre，则表示满足BST，然后将pre更新；反之，不满足BST
            if (node.val > pre6.val) {
                pre6 = node;
            } else {
                return false;
            }
        }

        //右
        boolean right = dfs6(node.right);

        return left && right;
    }

    /**
     * 参考dmsxl：错误解法！！!
     * <p>
     * 错误原因：
     * dmsxl中，maxValue是全局变量；
     * 而这里preVal是局部变量，意味着中序遍历时，左孩子的递归更新preVal后，当前节点无法感知。
     * 如，对于节点4，其左孩子为3；
     * 首先，左孩子更新后preVal=3，接着左孩子递归结束；
     * 然后，开始节点4执行【中】的逻辑，但此时preVal的值为节点4的父节点传递下来，并不是节点4左孩子更新的值；
     * 这意味着，preVal并不是，记录中序遍历结果中，当前节点的前一个元素值，所以也就无法通过preVal判断！！！！
     */
    public boolean isValidBST5(TreeNode root) {
        return dfs5(root, Long.MIN_VALUE);
    }

    public boolean dfs5(TreeNode node, Long preVal) {
        if (node == null) return true;

        // 左
        boolean left = dfs5(node.left, preVal);

        // 中
        // 当前节点与中序遍历结果的前一个节点值maxValue比较，若当前节点更大，则更新maxValue并且继续向下递归；反之，不是BST
        if (node.val > preVal) {
            preVal = (long) node.val;
        } else {
            return false;
        }

        // 右
        boolean right = dfs5(node.right, preVal);

        return left && right;
    }

    /**
     * dmsxl：dfs-递归-中序
     * <p>
     * 思路：
     * 1.中序遍历BST，其节点值严格递增；
     * 2.所以通过全局变量maxValue，记录中序遍历结果中，当前节点的前一个元素值；如[1,2,maxValue=7,4]，判断到节点4时，若是BST，那么应该有4 > maxValue，但实际4<7，所以不是BST。
     * 3.为什么使用Long.MIN_VALUE？——是因为，题目说明节点值 >= -2^31，若使用Integer.MIN_VALUE就无法判断-2^31。
     * <p>
     * 不足：
     * 如果题目改成节点值 >= Long.MIN_VALUE，那对于最小节点值也无法判断。
     * 后续可以优化为双指针，pre指向上一个节点（即pre指向，中序遍历结果中，当前节点的前一个元素值对应的节点）
     */
    Long maxValue = Long.MIN_VALUE;

    public boolean isValidBST4(TreeNode root) {
        if (root == null) return true;

        // 左
        boolean left = isValidBST4(root.left);

        // 中
        // 当前节点与中序遍历结果的前一个节点值maxValue比较，若当前节点更大，则更新maxValue并且继续向下递归；反之，不是BST
        if (root.val > maxValue) {
            maxValue = (long) root.val;
        } else {
            return false;
        }

        // 右
        boolean right = isValidBST4(root.right);

        return left && right;
    }

    // TODO 官解 先序递归不太理解，上下界的处理
    /**
     * 官解：dfs-递归-先序
     * <p>
     * 思路：与当前节点的上一个节点比较
     */
    public boolean isValidBST3(TreeNode root) {
        if (root == null) return true;

        return dfs3(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean dfs3(TreeNode node, Long min, Long max) {
        if (node == null) return true;

        // 根
        if (node.val <= min || node.val >= max) return false;

        // 左
        // 更新上界
        Long curMax = (long) node.val;
        boolean left = dfs3(node.left, min, curMax);
        // 右
        // 更新下界
        Long curMin = (long) node.val;
        boolean right = dfs3(node.right, curMin, max);

        return left && right;
    }

    /**
     * 个解：dfs-递归-先序（错误解法！！！）
     * <p>
     * 错误原因：
     * 本方法只保证，当前节点和它的左右孩子满足，node.left.val < node.val < node.right.val。
     * 忽略BST的一个特点。那就是，BST的左、右子树也是BST，意味着，左子树所有节点值都小于当前节点，右子树所有节点值都大于当前节点。
     * <p>
     * 错误案例：
     * [10, 5, 15, null, null, 6, 20]
     * 对于15为根的树来说，其左孩子6 < 15 < 右孩子20，所以15这棵树是BST；
     * 但是，15是root节点的右子树，所以15这棵树的所有节点都要 > 10，而15的左孩子6明显小于10，不满足BST。
     * <p>
     * 那么，如何判断node的左子树所有节点是否小于node的父节点（祖父节点）？node的右子树所有节点是否大于node的父节点？——参照dmsxl解法。
     */
    public boolean isValidBST2(TreeNode root) {
        if (root == null) return true;

        // 根
        if (root.left != null && root.left.val >= root.val) return false;
        if (root.right != null && root.right.val <= root.val) return false;
        // 左
        boolean left = isValidBST2(root.left);
        // 右
        boolean right = isValidBST2(root.right);

        return left && right;
    }

    /**
     * 官解
     * <p>
     * 思路：BST中序遍历结果是严格递增；所以先得到遍历结果，再判断是否严格递增
     */
    public boolean isValidBST(TreeNode root) {
        // 对于BST，中序遍历结果一定是严格递增；所以，先中序遍历，再判断是否严格递增，即可判断是否为一棵BST

        // 中序遍历
        List<Integer> vals = new ArrayList<>();
        preorder(root, vals);
        // 验证是否为BST
        for (int i = 0; i < vals.size() - 1; i++) {
            if (vals.get(i + 1) <= vals.get(i)) {
                return false;
            }
        }
        return true;
    }

    private void preorder(TreeNode root, List<Integer> vals) {
        // 1.返回值：无。入参：每层根节点，记录中序遍历节点值val的集合。
        // 2.终止条件：本层根节点为null。
        if (root == null) return;
        // 3.单层逻辑：递归左->根（先记录本层根节点值val）->递归右顺序
        preorder(root.left, vals);
        vals.add(root.val);
        preorder(root.right, vals);
    }

}
